Educational Codeforces Round 155 (Rated for Div. 2)

Rigged!

模拟。

public static void solve() {
    int n = io.nextInt();
    int[] s = new int[n];
    int[] e = new int[n];
    for (int i = 0; i < n; i++) {
        s[i] = io.nextInt();
        e[i] = io.nextInt();
    }
    for (int i = 1; i < n; i++) {
        if (s[i] >= s[0] && e[i] >= e[0]) {
            io.println(-1);
            return;
        }
    }
    io.println(s[0]);
}

Chips on the Board

有两种情况，每行都放一个或者每列都放一个，然后模拟即可。

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    int[] b = new int[n];
    long suma = 0L;
    int mina = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        suma += a[i];
        mina = Math.min(mina, a[i]);
    }
    long sumb = 0L;
    int minb = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
        sumb += b[i];
        minb = Math.min(minb, b[i]);
    }
    io.println(Math.min(suma + (long) minb * n, sumb + (long) mina * n));
}

Make it Alternating

所有连续重复数的个数就是最少操作次数，然后就是简单的应用组合数学。

private static final int MOD = 998244353;

public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    long cnt = n, sum = 1L;
    for (int i = 0; i < n; ) {
        int j = i + 1;
        while (j < n && s[j] == s[j - 1]) {
            j++;
        }
        sum = sum * (j - i) % MOD;
        cnt--;
        i = j;
    }
    for (long i = 1; i <= cnt; i++) {
        sum = sum * i % MOD;
    }
    io.println(cnt + " " + sum);
}

Sum of XOR Functions

固定右端点，然后分别考虑每一位，计算答案，公式如下：

$$ \sum_{r=1}^{n}\sum_{l=1}^{r}f(l,r)\cdot (r-l+1) =\sum_{r=1}^{n}\sum_{i=0}^{31}\sum_{l=1}^{r}(f_{i}(1,r)\oplus f_{i}(1,l-1))\cdot (r-(l-1)) $$

可以发现对于每一位，\(f_{i}(1,r)\oplus f_{i}(1,l-1)\) 的值不是 \(1\) 就是 \(0\)，只有当值为 \(1\) 时才会对答案有贡献。如果 \(f_{i}(1,r)=1\)，那么右端点 \(r\) 的第 \(i\) 位对答案的贡献为 \((cnt[i][0]\cdot r-sum[i][0])\cdot 2^{i}\)（其中 \(cnt[i][0]\) 表示前缀中 \(f_{i}=0\) 的个数，\(sum[i][0]\) 表示前缀中 \(f_{i}=0\) 的区间长度之和），另一种情况同理。

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt();
    int[] s = new int[n + 1];
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] ^ io.nextInt();
    }

    long ans = 0L;
    long[][] cnt = new long[32][2];
    long[][] sum = new long[32][2];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 32; j++) {
            int x = s[i] >> j & 1;
            ans = (ans + (cnt[j][x ^ 1] * i - sum[j][x ^ 1]) % MOD * (1 << j)) % MOD;
            cnt[j][x]++;
            sum[j][x] += i;
        }
    }
    io.println(ans);
}